package test.test;

import org.junit.Test;

import static org.junit.Assert.fail;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * https://leetcode.cn/contest/weekly-contest-397/problems/maximum-difference-score-in-a-grid/
 *
 * @author Hasee
 *
 */
public class C {
    /**
     * 从右下方起，dp[i][j]意为选择i,j位置拿到的最大值。
     * 下方最优：max(选下方最大的数，下方最大的a[x][j]+dp[x][j])-a[i][j]
     * 右方最优：max(选右方最大的数，右方最大的a[i][y]+dp[i][y])-a[i][j]
     * dp[i][j] = max(下方最优，右方最优)
     * 我们开两个数组，记录每一行的最大a[x][y]和最大q[x][y]+dp[x][y]，每一列的最大a[x][y]和最大q[x][y]+dp[x][y]
     * 通过上面的分析得到得分的最大值
     * @param grid
     * @return
     */
    public int maxScore(List<List<Integer>> grid) {
        int n = grid.size();
        int m = grid.get(0).size();
        int ans = Integer.MIN_VALUE;
        int[][] right = new int[n][2];  //每一行的最大a[x][y]和最大q[x][y]+dp[x][y]
        int[][] down = new int[m][2];   //每一列的最大a[x][y]和最大q[x][y]+dp[x][y]
        right[n - 1][0] = grid.get(n - 1).get(m - 1);
        right[n - 1][1] = right[n - 1][0];

        down[m - 1][0] = grid.get(n - 1).get(m - 1);
        down[m - 1][1] = down[m - 1][0];
        //预处理最后一行和最后一列
        for (int i = n - 2; i >= 0; i--) {
            Integer num = grid.get(i).get(m - 1);
            int cur = Math.max(right[i + 1][0], right[i + 1][1]) - num;   //dp[i][j]
            ans = Math.max(ans, cur);

            right[i][0] = Math.max(right[i + 1][0], num);
            right[i][1] = Math.max(right[i + 1][1], num + cur);
        }
        for (int i = m - 2; i >= 0; i--) {
            Integer num = grid.get(n - 1).get(i);
            int cur = Math.max(down[i + 1][0], down[i + 1][1]) - num;   //dp[i][j]
            ans = Math.max(ans, cur);

            down[i][0] = Math.max(down[i + 1][0], num);
            down[i][1] = Math.max(down[i + 1][1], num + cur);
        }
        //从右下方起，dp[i][j]意为选择i,j位置拿到的最大值
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                Integer num = grid.get(i).get(j);
                int choseDown = Math.max(down[j][0], down[j][1]) - num;
                int choseRight = Math.max(right[i][0], right[i][1]) - num;
                int cur = Math.max(choseDown, choseRight);
                ans = Math.max(ans, cur);

                down[j][0] = Math.max(down[j][0], num);
                down[j][1] = Math.max(down[j][1], num + cur);
                right[i][0] = Math.max(right[i][0], num);
                right[i][1] = Math.max(right[i][1], num + cur);
            }
        }

        return ans;
    }

    @Test
    public void test() {
        List<List<Integer>> grid = new ArrayList<>();
        grid.add(new ArrayList<Integer>() {{
            add(4);
            add(3);
            add(2);
        }});
        grid.add(new ArrayList<Integer>() {{
            add(3);
            add(2);
            add(1);
        }});
        int i = maxScore(grid);
        System.out.println(i);
    }
}
